package com.zhugang.week01;

/**
 * @program algorithms
 * @description: reverseWords
 * @author: chanzhugang
 * @create: 2022/05/21 22:48
 */
public class ReverseWords2 {
    public static void main(String[] args) {
        ReverseWords2 reverseWords2 = new ReverseWords2();

        String s = "the sky is blue";
        String s1 = reverseWords2.reverseWords2(s);
        System.out.println(s1);

    }

    /**
     * 剑指offer 58 -1. 翻转单词顺序
     *
     * @param s
     * @return
     */
    public String reverseWords(String s) {
        // 按空格分割成数组； 反向遍历数组追加到sb
        String[] strArr = s.split(" ");
        if (s.length() == 0) {
            return "";
        }
        if (strArr.length == 0) {
            return "";
        }
        StringBuilder sb = new StringBuilder();
        for (int i = strArr.length - 1; i >= 0; i--) {
            if (!strArr[i].isEmpty()) {
                sb.append(strArr[i]).append(" ");
            }
        }
        sb.delete(sb.length() - 1, sb.length());
        return sb.toString();
    }

    /**
     * 1次翻转， n次内部翻转
     *
     * @param s
     * @return
     */
    public String reverseWords2(String s) {
        // 去除空格； 整体翻转一次； 内部每个单词翻转
        char[] chars = s.toCharArray();
        int n = trim(chars);
        if (n == 0) {
            return "";
        }
        reverse(chars, 0, n - 1);
        int p = 0;
        while (p < n) {
            int r = p;
            while (r < n && chars[r] != ' ') {
                r++;
            }
            reverse(chars, p, r - 1);
            p = r + 1;
        }
        char[] newChar = new char[n];
        for (int i = 0; i < n; i++) {
            newChar[i] = chars[i];
        }
        return new String(newChar);
    }

    private void reverse(char[] chars, int p, int r) {
        while (p <= r) {
            char temp = chars[p];
            chars[p] = chars[r];
            chars[r] = temp;
            p++;
            r--;
        }
    }

    private int trim(char[] chars) {
        // 去除前置、后置、中间多余空格
        int n = chars.length;
        int i = 0;
        int j = n - 1;
        while (i < n && chars[i] == ' ') {
            i++;
        }
        while (j >= 0 && chars[j] == ' ') {
            j--;
        }

        int k = 0;
        while (i <= j) {
            if (chars[i] == ' ') {
                if (i + 1 <= j && chars[i + 1] != ' ') {
                    chars[k++] = ' ';
                }
            } else {
                chars[k++] = chars[i];
            }
            i++;
        }
        return k;
    }
}